package com.cn.codebrush.练习;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author Boolean
 * @Date 2022/5/22 21:33
 * @Version 1.0
 */
public class No15三数之和 {
    public static void main(String[] args) {

    }

    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(i>0 && nums[i] == nums[i-1]){continue;}
            if(nums[i]>0){break;}
            int left = i+1,right = n-1;
            while (left<right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while (left<right && nums[left] == nums[left+1]){left++;}
                    while (left<right && nums[right-1] == nums[right]){right--;}
                    left++;
                    right--;
                } else if(sum > 0){
                    right --;
                }else {
                    left ++;
                }
            }

        }

        return res;
    }
}
